package algorithms.a08MinimumSpanTrees;

import algorithms.a04heap.MinHeap;
import com.google.common.collect.Sets;

import java.net.URI;
import java.util.Iterator;
import java.util.Set;

/**
 * 使用Prim算法求图的最小生成树
 * 基础版
 * @author 王昊然
 * @create 2018-03-06 15:15
 **/
public class LazyPrimMST<Weight extends Number & Comparable> {

    private WeightedGraph<Weight> g;//图，前提是只有一个联通分量
    private MinHeap<Edge<Weight>> mh; //最小生成树的边组成的最小堆
    private boolean[] marked; //所有点，最小生成树的点标记为true
    private Set<Edge<Weight>> edges; //最小生成树边的集合
    private Number mstWeight;        // 最小生成树的权值（边权值的和）


    public LazyPrimMST(WeightedGraph<Weight> graph) {
        this.g = graph;
        mh = new MinHeap<Edge<Weight>>(g.E()); //极端情况会将所有边都放到最小堆里的
        marked = new boolean[g.V()];
        edges = Sets.newHashSet();
        mstWeight = new Double(0);

        startPrim(0);
    }


    /**
     * 从一个未标记的点开始（过程不太好理解，多看ppt的动画演示）
     * 1 遍历点的所有边，将属于横切边的都放入最小堆
     * 2 最小堆中取顶点的边：
     * 2-1如果边的两个点都没有被mark，说明当前边就是要找的一条边，放入最小树集合，计算权值和，visit另一个点
     * 2-2如果边的两个点都已经被mark，说明已经有其他路径将两点相连，该边废弃掉
     * 2-3不会存在两个点都未被标记的情况，这样的边是不会放到堆里的
     * 3 最小堆为空时停止
     *
     * @param v
     * @date: 2018/3/6 15:34
     * @author: 王昊然
     */
    private void startPrim(int v) {

        visit(v);

        while (!mh.isEmpty()) {
            Edge<Weight> minEdge = mh.extractMin();
            int p = marked[minEdge.V()] ? minEdge.W() : minEdge.V();//找边的两点中为false的点，先以v为标准
            if (!marked[p]) {//如果marked[p]仍为true，说明w、v都为已标记的点
                edges.add(minEdge);
                mstWeight = mstWeight.doubleValue() + minEdge.wt().doubleValue();
                visit(p);
            }
        }
    }

    /**
     * 将点连接的边，在当前情况下属于横切边的，都放到堆中
     * 注意“当前情况”的理解含义
     * @param v
     * @date: 2018/3/6 16:56
     * @author: 王昊然
     */
    private void visit(int v) {

        marked[v] = true;
        Iterator<Edge> iterator = g.adj(v).iterator();
        while (iterator.hasNext()) {
            Edge edge = iterator.next();
            if (!marked[edge.other(v)]) {//横切边
                mh.insert(edge);
            }
        }
    }

    // 返回最小生成树的所有边
    public Set<Edge<Weight>> mstEdges(){
        return edges;
    };

    // 返回最小生成树的权值
    public Number result(){
        return mstWeight;
    };

    public static void main(String[] args) throws Exception{

        URI fileUri = LazyPrimMST.class.getResource("testG1.txt").toURI();

        String filename = "testG1.txt";
        int V = 8;

        SparseWeightedGraph<Double> g = new SparseWeightedGraph<Double>(V, false);
        ReadWeightedGraph readGraph = new ReadWeightedGraph(g, fileUri);

        // Test Lazy Prim MST
        System.out.println("Test Lazy Prim MST:");
        LazyPrimMST<Double> lazyPrimMST = new LazyPrimMST<Double>(g);
        Set<Edge<Double>> mst = lazyPrimMST.mstEdges();
        Iterator<Edge<Double>> iterator = mst.iterator();
        while(iterator.hasNext())
            System.out.println(iterator.next());

        System.out.println("The MST weight is: " + lazyPrimMST.result());

        System.out.println();
    }

}
